public class Solution18 {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) return false;

        if (isSameTree(root, subRoot)) return true;

        // 递归在左子树和右子树中寻找子树
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    private boolean isSameTree(TreeNode s, TreeNode t) {
        // 都为空，说明完全相同
        if (s == null && t == null) return true;
        // 一个为空，一个不为空，或者值不同，返回 false
        if (s == null || t == null || s.val != t.val) return false;
        // 比较左右子树
        return isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
    }
}
